package algorithm.leetcode;

/**
 * @author: zhouj-j
 * @since: 2018/7/17
 */
public class __023_merge_k_list {
    public ListNode mergeKLists(ListNode[] lists) {
        MinHeap heap = new MinHeap(lists.length);
        for (ListNode node : lists) {
            if (node != null) {
                heap.insert(node);
            }
        }
        if (heap.isEmpty()) {
            return null;
        }
        ListNode head = heap.delMin();
        ListNode tail = head;
        if (tail.next != null) {
            heap.insert(tail.next);
        }
        while (!heap.isEmpty()) {
            ListNode curr = heap.delMin();
            if (curr.next != null) {
                heap.insert(curr.next);
            }
            tail.next = curr;
            tail = tail.next;
        }
        return head;
    }

    private class MinHeap {
        private ListNode[] heap;
        private int size;

        public MinHeap(int n) {
            this.heap = new ListNode[n + 1];
            size = 0;
        }

        public void insert(ListNode node) {
            heap[++size] = node;
            swim(size);
        }

        public ListNode delMin() {
            ListNode node = heap[1];
            heap[1] = heap[size];
            heap[size--] = null;
            sink(1);
            return node;
        }

        private void swim(int k) {
            while (k > 1 && less(k, k / 2)) {
                exch(k, k / 2);
                k = k / 2;
            }
        }

        public boolean isEmpty() {
            return size == 0;
        }

        private void sink(int k) {
            while (2 * k <= size) {
                int j = 2 * k;
                if (j < size && less(j + 1, j)) {
                    j = j + 1;
                }
                if (!less(j, k)) {
                    break;
                }
                exch(k, j);
                k = j;
            }
        }

        private boolean less(int n, int m) {
            return heap[n].val < heap[m].val;
        }

        private void exch(int n, int m) {
            ListNode t = heap[n];
            heap[n] = heap[m];
            heap[m] = t;
        }
    }

    class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }


    private void test() {
        ListNode node = new ListNode(1);
        node.next = new ListNode(4);
        node.next.next = new ListNode(5);

        ListNode node1 = new ListNode(1);
        node1.next = new ListNode(3);
        node1.next.next = new ListNode(4);

        ListNode node2 = new ListNode(2);
        node2.next = new ListNode(6);

        ListNode[] nodes = {node, node1, node2};

        ListNode head = mergeKLists(nodes);
        while (head != null) {
            System.out.print(head.val + "->");
            head = head.next;
        }
    }

    public static void main(String[] args) {
        new __023_merge_k_list().test();
    }
}
